#include<bits/stdc++.h>
#define lt id<<1
#define rt id<<1|1
#define fi first
#define se second
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int stk[20],tp;
inline void write(ll x)
{
    if(!x) return puts("0"),void();
    tp=0;
    while(x) stk[++tp]=x%10,x/=10;
    while(tp) putchar(stk[tp--]^48);
    putchar('\n');
}
const int N=1.5e5+10,M=N<<2;
int n,m,q,a[N],b[N];
int tag[M];
pi Mn[M];
ll ans;
void inc(int id,int x) {Mn[id].fi+=x,tag[id]+=x;}
void push_up(int id) {Mn[id]=min(Mn[lt],Mn[rt]);}
void push_down(int id)
{
    if(!tag[id]) return;
    inc(lt,tag[id]),inc(rt,tag[id]);
    tag[id]=0;
}
void build(int id,int l,int r)
{
    tag[id]=0;
    if(l==r) return Mn[id]=mk(a[l],r),void();
    int mid=(l+r)>>1;
    build(lt,l,mid),build(rt,mid+1,r);
    push_up(id);
}
void add(int id,int l,int r,int L,int R,int x)
{
    if(l>R||r<L) return;
    if(L<=l&&r<=R) return inc(id,x);
    push_down(id);
    int mid=(l+r)>>1;
    add(lt,l,mid,L,R,x);
    add(rt,mid+1,r,L,R,x);
    push_up(id);
}
pi query(int id,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return Mn[id];
    push_down(id);
    int mid=(l+r)>>1;
    if(R<=mid) return query(lt,l,mid,L,R);
    if(L>mid) return query(rt,mid+1,r,L,R);
    return min(query(lt,l,mid,L,R),query(rt,mid+1,r,L,R));
}
void solve(int l,int r)
{
    ans=0;
    build(1,l,r);
    // for(int i=l;i<=r;i++) b[i]=a[i];
    for(int i=l,R;i<=r;i++)
    {
        // if(!b[i]) continue;
        // int Mn=1e9;
        // for(int j=i;j<=i+m-1;j++)
        // {
        //     if(!b[j]) break;
        //     Mn=min(Mn,b[j]);
        // }
        // for(int j=i;j<=i+m-1;j++)
        // {
        //     if(!b[j]) break;
        //     b[j]-=Mn;
        // }
        // ans+=Mn;
        // if(b[i]) --i;
        R=min(r,i+m-1);
        pi x=query(1,l,r,i,R);
        if(!x.fi&&i==x.se) continue;
        if(!x.fi) R=x.se-1,x=query(1,l,r,i,x.se-1);
        ans+=x.fi,add(1,l,r,i,R,-x.fi);
        assert(query(1,l,r,i,i).fi>=0);
        if(query(1,l,r,i,i).fi) --i;
    }
    write(ans);
}
int main()
{
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    int l,r;
    while(q--)
        l=read(),r=read(),solve(l,r);
    return 0;
}